package com.simple.util.math;

/**
 * @program: simple_tools
 * @description: 支持各种类型快速排序工具
 * @author: ChenWenLong
 * @create: 2019-11-15 09:45
 **/
public class QuickSortUtil {

    /**
     * 功能描述:
     * 〈对指定数组进行分割〉
     *
     * @params : [a, p, r]
     * @return : int
     * @author : cwl
     * @date : 2019/11/15 9:42
     */
    private static int partitionInt(int a[],int p,int r){
        int x = a[r-1];
        int i = p - 1;
        int temp;
        for(int j=p;j<=r-1;j++){
            if(a[j-1]<=x){
                i++;
                temp = a[j-1];
                a[j-1] = a[i-1];
                a[i-1] = temp;
            }
        }
        temp = a[r-1];
        a[r-1] = a[i];
        a[i] = temp;
        return i+1;
    }

    /**
     * 功能描述:
     * 〈double类型快速排序〉
     *
     * @params : [a, p, r]
     * @return : int
     * @author : cwl
     * @date : 2019/11/15 9:47
     */
    private static int partitionDouble(double a[],int p,int r){
        double x = a[r-1];
        int i = p - 1;
        double temp;
        for(int j=p;j<=r-1;j++){
            if(a[j-1]<=x){
                i++;
                temp = a[j-1];
                a[j-1] = a[i-1];
                a[i-1] = temp;
            }
        }
        temp = a[r-1];
        a[r-1] = a[i];
        a[i] = temp;
        return i+1;
    }

    /**
     * 功能描述:
     * 〈Long类型快速排序〉
     *
     * @params : [a, p, r]
     * @return : int
     * @author : cwl
     * @date : 2019/11/15 9:49
     */
    private static int partitionLong(long a[],int p,int r){
        long x = a[r-1];
        int i = p - 1;
        long temp;
        for(int j=p;j<=r-1;j++){
            if(a[j-1]<=x){
                i++;
                temp = a[j-1];
                a[j-1] = a[i-1];
                a[i-1] = temp;
            }
        }
        temp = a[r-1];
        a[r-1] = a[i];
        a[i] = temp;
        return i+1;
    }

    /**
     * 功能描述:
     * 〈快速排序方法〉
     *
     * @params : [a, p, r]
     * @return : void
     * @author : cwl
     * @date : 2019/11/15 9:42
     */
    public static void quickSortInt(int a[],int p,int r){
        if(p < r){
            int q = partitionInt(a, p, r);
            quickSortInt(a, p, q-1);
            quickSortInt(a, q+1, r);
        }
    }

    /**
     * 功能描述:
     * 〈double类型快排〉
     *
     * @params : [a, p, r]
     * @return : void
     * @author : cwl
     * @date : 2019/11/15 9:48
     */
    public static void quickSortDouble(double a[],int p,int r){
        if(p < r){
            int q = partitionDouble(a, p, r);
            quickSortDouble(a, p, q-1);
            quickSortDouble(a, q+1, r);
        }
    }

    /**
     * 功能描述:
     * 〈Long类型快排〉
     *
     * @params : [a, p, r]
     * @return : void
     * @author : cwl
     * @date : 2019/11/15 9:51
     */
    public static void quickSortLong(double a[],int p,int r){
        if(p < r){
            int q = partitionDouble(a, p, r);
            quickSortDouble(a, p, q-1);
            quickSortDouble(a, q+1, r);
        }
    }
}
